package com.cskaoyan.javase.recursion._1basic;

/**
 * 递归的思想:
 * 引例：
 * 使用递归计算N（N>=1）的阶乘（factorial）
 * N! = N *(N-1)*(N-2)*...*1;
 *
 * 可以考虑两种解法:
 *      1.循环,当需要重复运行一段代码时,考虑使用循环
 *          使用循环,最重要的是要找到循环体语句
 *          N! = N *(N-1)*(N-2)*...*1;
 *          实际上就是累乘,用循环做很简单
 *
 *      2.递归,要想用递归,需要首先找到递归体语句
 *          递归体语句是在方法内部再次调用自身方法
 *          这说明递归求解问题是把大规模的问题分解成相似解法的小规模问题
 *          递归的思想就是分解的思想:
 *              a.把一个复杂的大规模的问题，分解成若干相似的小规模的子问题。
 *              b.当子问题规模足够小的时候，就可以直接得到小规模问题的解。
 *              c.然后把所有的小规模的子问题的解
 *                  组合起来，得到要求解的大规模问题的解。
 *          N! = N * (N-1)!
 *          (N-1)! =(N-1) * (N-2)!
 *          ...
 *          以上分解就可以找到递归的递归体:N! = N * (N-1)!
 *          而且分解不是无限制进行的
 *          当问题的规模已经很小了,分解会有不能分解的时候,这就是递归的出口
 *          1! = 1 就是递归的出口
 *
 * 递归的优缺点
 * 不难发现递归的优点是：
 *      1.递归的代码会非常简洁，这是最直观的。
 *      2.人在解决问题的时候，都会下意识的分解问题。
 *          递归的思想很符合人的思维，用递归求解一个问题的思路很容易被人理解。
 *      3.接第二条，一旦能够找打分解问题的思路，递归会非常好用。
 *
 * 递归的缺点:
 *      1.不用递归时，往往一个方法就能解决问题。
 *      而递归会调用多个方法，占用大量栈内存，且明显存在重复计算，效率低。
 *      也就是说，使用递归求解一个问题，时间和空间复杂度都不占优势，既占用空间效率还低。
 *      2.栈溢出错误警告！递归很危险，一旦栈溢出是严重错误！
 *
 * @since 11:14
 * @author wuguidong@cskaoyan.onaliyun.com
 */
public class Demo {
    public static void main(String[] args) {
        System.out.println(factorialLoopSolution(10));
        System.out.println(factorialRecursionSolution(10));
    }

    public static int factorialRecursionSolution(int n) {
        // 递归的出口
        if (n == 1) {
            return 1;
        }
        // 递归体
        return n * factorialRecursionSolution(n - 1);
    }

    public static int factorialLoopSolution(int n) {
        int product = 1;
        for (int i = 1; i <= n; i++) {
            product *= i;
        }
        return product;
    }
}
